package org.richin.collection.util;

import java.util.AbstractSequentialList;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Map;
import java.util.Random;
import java.util.RandomAccess;
import java.util.Set;

import javax.annotation.Nonnull;

import org.richin.array.util.ArrayUtils;
import org.richin.lang.util.Convert;
import org.richin.lang.util.ObjectUtils;
import org.richin.lang.util.StringUtils;

public class ListUtils extends org.apache.commons.collections.ListUtils {
	/**
	 * angesprochenes Element mit dem darberliegenden Element tauschen, wodurch
	 * das Element eine Position nach oben bewegt wird
	 * 
	 * @param movePos
	 */
	public static <E> ArrayList<E> moveUp(ArrayList<E> arrList, int movePos) {
		if (movePos > 0 && movePos < arrList.size()) {
			E tmpObject = arrList.get(movePos);

			arrList.set(movePos, arrList.get(movePos - 1));
			arrList.set(movePos - 1, tmpObject);
		}
		return arrList;
	} // end method moveUp
	public static List<?> toList(Iterator<?> iter) {
		List<Object> list = new ArrayList<Object>();
		while ( iter.hasNext() ) {
			list.add( iter.next() );
		}
		return list;
	}
	public static <E> ArrayList<E> moveDn(ArrayList<E> arrList, int movePos) {
		if (movePos > -1 && movePos < arrList.size() - 1) {
			E tmpObject = arrList.get(movePos);

			arrList.set(movePos, arrList.get(movePos + 1));
			arrList.set(movePos + 1, tmpObject);
		}
		return arrList;
	} // end method moveDn

	/**
	 * ArrayList aufw&auml;rts sortieren . <br/> Die ArrayList-Elemente
	 * m&uuml;ssen das Interface <b>java.lang.Comparable<b/> implementieren.
	 */
	@SuppressWarnings("unchecked")
	public static <E> ArrayList<E> sortUp(ArrayList<E> arrList) {
		for (int lauf = 0; lauf <= arrList.size(); lauf++) {
			for (int pos = 0; pos < arrList.size() - 1; pos++) {
				if (((Comparable<E>) arrList.get(pos)).compareTo(arrList.get(pos + 1)) > 0) {
					E puffer = arrList.get(pos);

					arrList.set(pos, arrList.get(pos + 1));
					arrList.set(pos + 1, puffer);
				}
			}
		}
		return arrList;
	} // end method sort

	public static <E> ArrayList<E> unique(ArrayList<E> arrList) {
		Set<E> set = new HashSet<E>(arrList);
		// set.addAll(arrList);
		arrList.clear();
		arrList.addAll(set);
		return arrList;
	}

	public static <E> String toString(ArrayList<E> arrList) {
		StringBuilder sb = new StringBuilder(arrList.size());
		for (E e : arrList)
			sb.append(e.toString() + ",");
		return sb.toString();
	}

	public <E> boolean add(ArrayList<E> arrList, E e) {
		if (arrList != null) {
			arrList.add(e);
		}
		return false;

	}

	/**
	 * 支持负数的GET
	 * 
	 * @param <E>
	 * @param arrList
	 * @param index
	 * @return
	 */
	public static <E> E get(ArrayList<E> arrList, int index) {
		int size = arrList == null ? 0 : arrList.size();
		if (index >= size)
			throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
		else if (index < 0)
			return get(arrList, size + index);

		return arrList.get(index);

	}

	/**
	 * 能够向数组那样在new的同时进行初始化
	 * List<Integer> intList = Lists.newArrayList(1,2);
	 * @param <E>
	 * @param elements
	 * @return
	 */
	public static <E> ArrayList<E> newArrayList(E... elements) {
		// Avoid integer overflow when a large array is passed in
		int capacity = computeArrayListCapacity(elements.length);
		ArrayList<E> list = new ArrayList<E>(capacity);
		Collections.addAll(list, elements);
		return list;
	}

	private static int computeArrayListCapacity(int arraySize) {
		if (arraySize < 0)
			throw new IllegalArgumentException();
		return (int) Math.min(5L + arraySize + (arraySize / 10), Integer.MAX_VALUE);
	}

	public static <E> ArrayList<E> newArrayList(Iterable<? extends E> elements) {
		// Let ArrayList's sizing logic work, if possible
		if (elements instanceof Collection) {
			@SuppressWarnings("unchecked")
			Collection<? extends E> collection = (Collection<? extends E>) elements;
			return new ArrayList<E>(collection);
		} else {
			return newArrayList(elements.iterator());
		}
	}

	public static <E> ArrayList<E> newArrayList(Iterator<? extends E> elements) {
		ArrayList<E> list = new ArrayList<E>();
		while (elements.hasNext()) {
			list.add(elements.next());
		}
		return list;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		ArrayList<String> arrayList = new ArrayList<String>();
		// for (int i = 0; i < 20; i++)
		arrayList.add("啊");
		arrayList.add("的");
		arrayList.add("各个");
		arrayList.add("的");
		arrayList.add("d");
		arrayList.add("d");
		arrayList.add("看");
		arrayList.add("吖");
		arrayList.add("地方");
		// arrayList.
		System.out.println(get(arrayList, -9));
		ArrayList<Integer> ggArrayList = newArrayList(3, 4, 5, 6);
		/*
		 * arrayList = moveUp(arrayList, 3); arrayList = moveDn(arrayList, 8);
		 * arrayList = sortUp(arrayList); arrayList = unique(arrayList);
		 * System.out.println(toString(arrayList)); for (int i = 0; i <
		 * arrayList.size(); i++) System.out.println(arrayList.get(i));
		 */
		//Collections.c
	}

	public static final <E> boolean hasAtLeastOne(List<E> list) {
		if (list != null && list.size() >= 1)
			return true;
		return false;
	} // end if

	public static <E> boolean contains(List<E> list, String in) {
		if (hasAtLeastOne(list) && StringUtils.isNotEmpty(in)) {
			for (Iterator<E> iter = list.iterator(); iter.hasNext();) {
				if (StringUtils.equals(StringUtils.objectToString(iter.next()), in)) {
					return true;
				}
			} // end for
		} // end if

		return false;
	} // end

	public static <E> List<E> fromArray(E[] o) {
		return fromArray(o, 0, new LinkedList<E>());
	}

	private static <E> List<E> fromArray(E[] o, int index, List<E> newList) {
		if (index >= o.length)
			return newList;
		newList.add(o[index]);
		return fromArray(o, index + 1, newList);
	}

	/**
	* Make a list of objects unique while retaining the original order.
	* @param a_list The original list with duplicate objects
	* @return the distinct list of objects.
	*/
	public static <E, V> List<E> unique(List<E> a_list) {
		List<E> distinctList = new ArrayList<E>();

		Map<E, V> distinctMap = new HashMap<E, V>();
		E e;
		int size = a_list.size();
		for (int index = 0; index < size; index++) {
			e = a_list.get(index);
			if (!distinctMap.containsKey(e)) {
				distinctMap.put(e, null);
				distinctList.add(e);
			}
		}

		return distinctList;
	}

	/**
	 * Make a list of duplicate objects while retaining the original order.
	 * @param a_list The original list with duplicate objects
	 * @return the duplicate list of objects.
	 */
	public static <E, V> List<E> duplicate(List<E> a_list) {
		List<E> duplicateList = new ArrayList<E>();

		Map<E, V> duplicateMap = new HashMap<E, V>();
		E e;
		int size = a_list.size();
		for (int index = 0; index < size; index++) {
			e = a_list.get(index);
			if (duplicateMap.containsKey(e)) {
				duplicateList.add(e);
			} else {
				duplicateMap.put(e, null);
			}
		}

		return duplicateList;
	}

	/**
	 * 获取反集
	 * @param <E>
	 * @param fromList
	 * @param excludeList
	 * @return
	 */
	public static <E> List<E> excludeList(List<E> fromList, List<E> excludeList) {
		if (fromList == null)
			return null;
		if (excludeList == null)
			return fromList;
		List<E> result = new ArrayList<E>(fromList.size());
		E e;
		for (int i = 0; i < fromList.size(); i++) {
			e = fromList.get(i);
			if (!excludeList.contains(e)) {
				result.add(e);
			}
		}

		return result;
	}

	/**
	* Returns a {@link java.util.List} from an array of {@link java.lang.Object}s,
	* returning an empty List if the array is <code>null</code>.
	*
	* @param p_objects the array of {@link java.lang.Object}s to be converted to
	* a {@link java.util.List}.
	*
	* @return a {@link java.util.List} of {@link java.lang.Object}s.
	*/
	public static <T> List<T> asList(T... p_objects) {
		if (ArrayUtils.sizeOf(p_objects) == 0) {
			return Collections.emptyList();
		}
		return Arrays.asList(p_objects);
	}

	/**
	* Combines two collections into one by concatenating the two, treating null
	* collections as empty collections.
	*
	* @param p_coll1 the first collection.
	* @param p_coll2 the second collection.
	*
	* @return a list that combines the two collections by concatenation.
	*/
	public static <T> List<T> concat(Collection<T> p_coll1, Collection<T> p_coll2) {
		List<T> list = new ArrayList<T>();

		if (p_coll1 != null) {
			list.addAll(p_coll1);
		}
		if (p_coll2 != null) {
			list.addAll(p_coll2);
		}
		return list;
	}

	/**
	 * Flattens a collection of collections into a collection.
	 *
	 * @param p_coll the collection to flatten.
	 *
	 * @return a new List that contains the flattened items.
	 */
	public static <T> List<T> flatten(Collection<? extends Collection<T>> p_coll) {
		List<T> result = new ArrayList<T>();

		for (Collection<T> coll : iterable(p_coll)) {
			result.addAll(coll);
		}
		return result;
	}

	/**
	 * Returns the {@link java.util.Iterator} for the specified collection, or an
	 * empty iterator if the collection is <code>null</code>, to avoid
	 * <code>NullPointerException</code>s.
	 */
	public static <T> Iterator<? extends T> iterator(Collection<? extends T> p_coll) {
		if (p_coll == null) {
			return new EmptyIterator<T>();
		}
		return p_coll.iterator();
	}

	/**
	 * Returns the <code>Iterable</code> for the specified collection, or an
	 * empty <code>Iterable</code> if the collection is <code>null</code>, to avoid
	 * <code>NullPointerException</code>s.
	 */
	public static <T> Iterable<? extends T> iterable(Collection<? extends T> p_coll) {
		if (p_coll == null) {
			return new EmptyIterable<T>();
		}
		return p_coll;
	}

	public static <E> Map<E, Integer> getIndexMap(List<E> list) {
		Map<E, Integer> indexes = new HashMap<E, Integer>();
		int index = 0;
		for (Iterator<E> it = list.iterator(); it.hasNext();) {
			indexes.put(it.next(), new Integer(index++));
		}
		return indexes;
	}

	final static public <E> E GetFirstEntry(Collection<E> collection) {
		if ((collection == null) || collection.isEmpty()) {
			return null;
		}
		return collection.iterator().next();
	}

	final static public <K, V> K GetFirstEntryKey(Map<K, V> map) {
		if ((map == null) || map.isEmpty()) {
			return null;
		}
		return GetFirstEntry(map).getKey();
	}

	final static public <K, V> V GetFirstEntryValue(Map<K, V> map) {
		if ((map == null) || map.isEmpty()) {
			return null;
		}
		return GetFirstEntry(map).getValue();
	}

	final static public <K, V> Map.Entry<K, V> GetFirstEntry(Map<K, V> map) {
		if ((map == null) || map.isEmpty()) {
			return null;
		}
		return map.entrySet().iterator().next();
	}

	public final static Map FilterEntries(Map map, Class clazz) {
		Map resultMap = new HashMap(map.size());
		if ((map == null) || map.isEmpty()) {
			return resultMap;
		}
		Iterator entries = map.entrySet().iterator();
		while (entries.hasNext()) {
			Map.Entry entry = (Map.Entry) entries.next();
			if (clazz.isInstance(entry.getValue())) {
				resultMap.put(entry.getKey(), entry.getValue());
			}
		}
		return resultMap;
	}

	public static <T> void removeNulls(Collection<T> list) {
		for (Iterator<T> iter = list.iterator(); iter.hasNext();) {
			T e = iter.next();
			if (e == null)
				iter.remove();
		}
	}

	public static <V> Iterable<V> reverse(final List<V> list) {
		return new Iterable<V>() {
			public Iterator<V> iterator() {
				final ListIterator<V> it = list.listIterator(list.size());
				return new Iterator<V>() {

					public boolean hasNext() {
						return it.hasPrevious();
					}

					public V next() {
						return it.previous();
					}

					public void remove() {
						it.remove();
					}
				};
			}
		};
	}

	/**
	 * 将一个集合按照固定大小查分成若干个集合。
	 *
	 * @param list
	 * @param count
	 * @return
	 */
	public static <E> List<E> split(final List<E> list, final int count) {
		List<E> subIdLists = new ArrayList<E>();
		if (list.size() < count) {
			subIdLists.addAll(list);
		} else {
			int i = 0;
			while (i < list.size()) {
				int end = i + count;
				if (end > list.size()) {
					end = list.size();
				}
				subIdLists.addAll(list.subList(i, end));
				i += count;
			}
		}
		return subIdLists;
	}

	/**
	 * 移动列表中的元素
	 * @param list 列表
	 * @param start 移动的元素的开始索引
	 * @param end 移动的元素的最后索引，不包括这个
	 * @param to 移动到的位置
	 * @since  0.5
	 */
	public static <E> void moveElements(List<E> list, int start, int end, int to) {
		List<E> subList = new ArrayList<E>(list.subList(start, end));
		list.removeAll(subList);
		list.addAll(to, subList);
	}

	public static <E> List<E> subList(List<E> list, int fromIndex, int toIndex) {
		return CollectionUtils.isNotEmpty(list) ? list.subList(fromIndex, toIndex) : null;

	}

	/**
	   * Perform a binary search of a List for a key, using the natural ordering of
	   * the elements. The list must be sorted (as by the sort() method) - if it is
	   * not, the behavior of this method is undefined, and may be an infinite
	   * loop. Further, the key must be comparable with every item in the list. If
	   * the list contains the key more than once, any one of them may be found.
	   * <p>
	   *
	   * This algorithm behaves in log(n) time for {@link RandomAccess} lists,
	   * and uses a linear search with O(n) link traversals and log(n) comparisons
	   * with {@link AbstractSequentialList} lists. Note: although the
	   * specification allows for an infinite loop if the list is unsorted, it will
	   * not happen in this (Classpath) implementation.
	   *
	   * @param l the list to search (must be sorted)
	   * @param key the value to search for
	   * @return the index at which the key was found, or -n-1 if it was not
	   *         found, where n is the index of the first value higher than key or
	   *         a.length if there is no such value
	   * @throws ClassCastException if key could not be compared with one of the
	   *         elements of l
	   * @throws NullPointerException if a null element has compareTo called
	   * @see #sort(List)
	   */
	public static <E> int binarySearch(List<E> l, E key) {
		return binarySearch(l, key, null);
	}

	/**
	 * Perform a binary search of a List for a key, using a supplied Comparator.
	 * The list must be sorted (as by the sort() method with the same Comparator)
	 * - if it is not, the behavior of this method is undefined, and may be an
	 * infinite loop. Further, the key must be comparable with every item in the
	 * list. If the list contains the key more than once, any one of them may be
	 * found. If the comparator is null, the elements' natural ordering is used.
	 * <p>
	 *
	 * This algorithm behaves in log(n) time for {@link RandomAccess} lists,
	 * and uses a linear search with O(n) link traversals and log(n) comparisons
	 * with {@link AbstractSequentialList} lists. Note: although the
	 * specification allows for an infinite loop if the list is unsorted, it will
	 * not happen in this (Classpath) implementation.
	 *
	 * @param l the list to search (must be sorted)
	 * @param key the value to search for
	 * @param c the comparator by which the list is sorted
	 * @return the index at which the key was found, or -n-1 if it was not
	 *         found, where n is the index of the first value higher than key or
	 *         a.length if there is no such value
	 * @throws ClassCastException if key could not be compared with one of the
	 *         elements of l
	 * @throws NullPointerException if a null element is compared with natural
	 *         ordering (only possible when c is null)
	 * @see #sort(List, Comparator)
	 */
	public static <E> int binarySearch(List<E> l, E key, Comparator<E> c) {
		int pos = 0;
		int low = 0;
		int hi = l.size() - 1;

		// We use a linear search with log(n) comparisons using an iterator
		// if the list is sequential-access.
		if (isSequential(l)) {
			ListIterator<E> itr = l.listIterator();
			int i = 0;
			while (low <= hi) {
				pos = (low + hi) >> 1;
				if (i < pos)
					for (; i != pos; i++, itr.next())
						;
				else
					for (; i != pos; i--, itr.previous())
						;
				final int d = CollectionUtils.compare(key, itr.next(), c);
				if (d == 0)
					return pos;
				else if (d < 0)
					hi = pos - 1;
				else
					// This gets the insertion point right on the last loop
					low = ++pos;
			}
		} else {
			while (low <= hi) {
				pos = (low + hi) >> 1;
				final int d = CollectionUtils.compare(key, l.get(pos), c);
				if (d == 0)
					return pos;
				else if (d < 0)
					hi = pos - 1;
				else
					// This gets the insertion point right on the last loop
					low = ++pos;
			}
		}

		// If we failed to find it, we do the same whichever search we did.
		return -pos - 1;
	}

	private static final int LARGE_LIST_SIZE = 16;

	/**
	 * Determines if a list should be treated as a sequential-access one.
	 * Rather than the old method of JDK 1.3 of assuming only instanceof
	 * AbstractSequentialList should be sequential, this uses the new method
	 * of JDK 1.4 of assuming anything that does NOT implement RandomAccess
	 * and exceeds a large (unspecified) size should be sequential.
	 *
	 * @param l the list to check
	 * @return true if it should be treated as sequential-access
	 */
	private static <E> boolean isSequential(List<E> l) {
		return !(l instanceof RandomAccess) && l.size() > LARGE_LIST_SIZE;
	}

	/**
	 * Copy one list to another. If the destination list is longer than the
	 * source list, the remaining elements are unaffected. This method runs in
	 * linear time.
	 *
	 * @param dest the destination list
	 * @param source the source list
	 * @throws IndexOutOfBoundsException if the destination list is shorter
	 *         than the source list (the destination will be unmodified)
	 * @throws UnsupportedOperationException if dest.listIterator() does not
	 *         support the set operation
	 */
	public static <E> void copy(List<E> dest, List<E> source) {
		int pos = source.size();
		if (dest.size() < pos)
			throw new IndexOutOfBoundsException("Source does not fit in dest");

		Iterator<E> i1 = source.iterator();
		ListIterator<E> i2 = dest.listIterator();

		while (--pos >= 0) {
			i2.next();
			i2.set(i1.next());
		}
	}

	/**
	 * Replace all instances of one object with another in the specified list.
	 * The list does not change size. An element e is replaced if
	 * <code>oldval == null ? e == null : oldval.equals(e)</code>.
	 *
	 * @param list the list to iterate over
	 * @param oldval the element to replace
	 * @param newval the new value for the element
	 * @return true if a replacement occurred
	 * @throws UnsupportedOperationException if the list iterator does not allow
	 *         for the set operation
	 * @throws ClassCastException newval is of a type which cannot be added
	 *         to the list
	 * @throws IllegalArgumentException some other aspect of newval stops
	 *         it being added to the list
	 * @since 1.4
	 */
	public static <E> boolean replaceAll(List<E> list, E oldval, E newval) {
		ListIterator<E> itr = list.listIterator();
		boolean replace_occured = false;
		for (int i = list.size(); --i >= 0;)
			if (ObjectUtils.equals(oldval, itr.next())) {
				itr.set(newval);
				replace_occured = true;
			}
		return replace_occured;
	}

	/**
	 * Rotate the elements in a list by a specified distance. After calling this
	 * method, the element now at index <code>i</code> was formerly at index
	 * <code>(i - distance) mod list.size()</code>. The list size is unchanged.
	 * <p>
	 *
	 * For example, suppose a list contains <code>[t, a, n, k, s]</code>. After
	 * either <code>Collections.rotate(l, 4)</code> or
	 * <code>Collections.rotate(l, -1)</code>, the new contents are
	 * <code>[s, t, a, n, k]</code>. This can be applied to sublists to rotate
	 * just a portion of the list. For example, to move element <code>a</code>
	 * forward two positions in the original example, use
	 * <code>Collections.rotate(l.subList(1, 3+1), -1)</code>, which will
	 * result in <code>[t, n, k, a, s]</code>.
	 * <p>
	 *
	 * If the list is small or implements {@link RandomAccess}, the
	 * implementation exchanges the first element to its destination, then the
	 * displaced element, and so on until a circuit has been completed. The
	 * process is repeated if needed on the second element, and so forth, until
	 * all elements have been swapped.  For large non-random lists, the
	 * implementation breaks the list into two sublists at index
	 * <code>-distance mod size</code>, calls {@link #reverse(List)} on the
	 * pieces, then reverses the overall list.
	 *
	 * @param list the list to rotate
	 * @param distance the distance to rotate by; unrestricted in value
	 * @throws UnsupportedOperationException if the list does not support set
	 * @since 1.4
	 */
	public static <E> void rotate(List<E> list, int distance) {
		int size = list.size();
		distance %= size;
		if (distance == 0)
			return;
		if (distance < 0)
			distance += size;

		if (isSequential(list)) {
			reverse(list);
			reverse(list.subList(0, distance));
			reverse(list.subList(distance, size));
		} else {
			// Determine the least common multiple of distance and size, as there
			// are (distance / LCM) loops to cycle through.
			int a = size;
			int lcm = distance;
			int b = a % lcm;
			while (b != 0) {
				a = lcm;
				lcm = b;
				b = a % lcm;
			}

			// Now, make the swaps. We must take the remainder every time through
			// the inner loop so that we don't overflow i to negative values.
			while (--lcm >= 0) {
				E o = list.get(lcm);
				for (int i = lcm + distance; i != lcm; i = (i + distance) % size)
					o = list.set(i, o);
				list.set(lcm, o);
			}
		}
	}

	/**
	 * Shuffle a list according to a default source of randomness. The algorithm
	 * used iterates backwards over the list, swapping each element with an
	 * element randomly selected from the elements in positions less than or
	 * equal to it (using r.nextInt(int)).
	 * <p>
	 *
	 * This algorithm would result in a perfectly fair shuffle (that is, each
	 * element would have an equal chance of ending up in any position) if r were
	 * a perfect source of randomness. In practice the results are merely very
	 * close to perfect.
	 * <p>
	 *
	 * This method operates in linear time. To do this on large lists which do
	 * not implement {@link RandomAccess}, a temporary array is used to acheive
	 * this speed, since it would be quadratic access otherwise.
	 *
	 * @param l the list to shuffle
	 * @throws UnsupportedOperationException if l.listIterator() does not
	 *         support the set operation
	 */
	public static <E> void shuffle(List<E> l) {
		if (defaultRandom == null) {
			synchronized (Collections.class) {
				if (defaultRandom == null)
					defaultRandom = new Random();
			}
		}
		shuffle(l, defaultRandom);
	}

	/**
	 * Cache a single Random object for use by shuffle(List). This improves
	 * performance as well as ensuring that sequential calls to shuffle() will
	 * not result in the same shuffle order occurring: the resolution of
	 * System.currentTimeMillis() is not sufficient to guarantee a unique seed.
	 */
	private static Random defaultRandom = null;

	/**
	 * Shuffle a list according to a given source of randomness. The algorithm
	 * used iterates backwards over the list, swapping each element with an
	 * element randomly selected from the elements in positions less than or
	 * equal to it (using r.nextInt(int)).
	 * <p>
	 *
	 * This algorithm would result in a perfectly fair shuffle (that is, each
	 * element would have an equal chance of ending up in any position) if r were
	 * a perfect source of randomness. In practise (eg if r = new Random()) the
	 * results are merely very close to perfect.
	 * <p>
	 *
	 * This method operates in linear time. To do this on large lists which do
	 * not implement {@link RandomAccess}, a temporary array is used to acheive
	 * this speed, since it would be quadratic access otherwise.
	 *
	 * @param l the list to shuffle
	 * @param r the source of randomness to use for the shuffle
	 * @throws UnsupportedOperationException if l.listIterator() does not
	 *         support the set operation
	 */
	public static <E> void shuffle(List<E> l, Random r) {
		int lsize = l.size();
		ListIterator<E> i = l.listIterator(lsize);
		boolean sequential = isSequential(l);
		E[] a = null; // stores a copy of the list for the sequential case

		if (sequential)
			a = (E[]) l.toArray();

		for (int pos = lsize - 1; pos > 0; --pos) {
			// Obtain a random position to swap with. pos + 1 is used so that the
			// range of the random number includes the current position.
			int swap = r.nextInt(pos + 1);

			// Swap the desired element.
			E o;
			if (sequential) {
				o = a[swap];
				a[swap] = i.previous();
			} else
				o = l.set(swap, i.previous());

			i.set(o);
		}
	}

	/**
	* Transposes an array of lists.
	*
	* @param lists the given lists
	* @return a List of the transposed lists
	* @see #transpose(List)
	*/
	@SuppressWarnings("unchecked")
	public static List transpose(Object... lists) {
		return transpose(Arrays.asList(lists));
	}

	/**
	 * Transposes the given lists.
	 * So, <code>transpose([['a', 'b'], [1, 2]])</code>
	 * is <code>[['a', 1], ['b', 2]]</code> and
	 * <code>transpose([['a', 'b', 'c']])</code>
	 * is <code>[['a'], ['b'], ['c']]</code>.
	 *
	 * @param lists the given lists
	 * @return a List of the transposed lists
	 */
	public static List transpose(List lists) {
		List result = new ArrayList();
		if (lists.isEmpty() || lists.size() == 0)
			return result;
		int minSize = Integer.MAX_VALUE;
		try {
			for (Iterator outer = lists.iterator(); outer.hasNext();) {
				List list = (List) Convert.castToType(outer.next(), List.class);

				if (list.size() < minSize)
					minSize = list.size();
			}
			if (minSize == 0)
				return result;
			for (int i = 0; i < minSize; i++) {
				result.add(new ArrayList());
			}
			for (Iterator outer = lists.iterator(); outer.hasNext();) {
				List list = (List) Convert.castToType(outer.next(), List.class);
				for (int i = 0; i < minSize; i++) {
					List resultList = (List) result.get(i);
					resultList.add(list.get(i));
				}
			}
		} catch (IllegalAccessException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		return result;
	}

	public static <E> Map<E, Integer> count(@Nonnull
	Collection<E> coll) {
		if (CollectionUtils.isEmpty(coll))
			return Collections.emptyMap();
		Map<E, Integer> sum = new HashMap<E, Integer>(coll.size());
		for (Iterator<E> it = coll.iterator(); it.hasNext();) {
			E e = it.next();
			Integer num = sum.put(e, 1);
			if (num != null)
				sum.put(e, num + 1);
		}
		return sum;
	}

	public static List<String> toList(String self) {
		if (StringUtils.isBlank(self))
			return new ArrayList<String>();
		int size = self.length();
		List<String> answer = new ArrayList<String>(size);
		for (int i = 0; i < size; i++) {
			answer.add(self.substring(i, i + 1));
		}
		return answer;
	}

	public static <E> boolean isEmpty(List<E> list) {
		return CollectionUtils.isEmpty(list);
	}

	public static <E> boolean isNotEmpty(List<E> list) {
		return !isEmpty(list);
	}

	/**
	 * 合并两个List的数据,只保留相同的数据.就是两个集合的交集<br>
	 * <code>
	 * lst1 : [1,2,3] <br>
	 * lst2 : [2,3]<br>
	 * uninonList result is [2,3]</code>
	 *
	 * @param <V>
	 * @param lst1
	 * @param lst2
	 * @return
	 */
	public static <V> List<V> unionList(List<V> lst1, List<V> lst2) {
		List<V> lst = new ArrayList<V>();

		if (lst1 == null && lst2 == null) {
			return lst;
		}
		if (lst1 == null) {
			return lst2;
		}
		if (lst2 == null) {
			return lst1;
		}

		for (V v : lst1) {
			if (lst2.contains(v)) {
				lst.add(v);
			}
		}
		return lst;
	}
	/**
     * Transform a list to a set of unique values. The order, in which the
     * elements appears, is preserved.
     *
     * @param <E>
     * @param list
     * @return
     */
    static public <E> Set<E> toSet(List<E> list) {
            Set<E> set = new LinkedHashSet<E>();
            for (E e : list) {
                    set.add(e);
            }

            return set;
    }

}
